#include "config.h"

#include <clx/libECM.h>
#include <clx/ecm_list.h>

#include "blockcache.h"

#undef PARANOIA

static LIST_HEAD(free_list);
static LIST_HEAD(intervals);

static ecm_uint32	n_intervals;

static ecm_hashtable_t	hash_session;

#ifdef COLLECT_CBLK
#define CBLK_COLLECT_ENABLED	ECM_TRUE
#define POLICY_NAME		"ICC"
#else
#define CBLK_COLLECT_ENABLED	ECM_FALSE
#define POLICY_NAME		"IC"
#endif

static ECMBOOL	cblk_collect_enabled = CBLK_COLLECT_ENABLED;

/* For simplicity, do not care performance */

struct _session;

typedef struct {
	ecm_uint32	size;
	struct _session	*follower;
	struct _session	*precedent;
	struct list_head	cblks;
	/* for sorting */
	struct list_head	list;
	struct list_head	list_media;
} interval_t;

typedef struct {
	ecm_uint32	mid;
	ecm_uint32	bid_max;
	struct _session		*session;	/* solo session which cannot form interval */
	struct list_head	intervals;
} media_t;

typedef struct {
	bcache_t	*bcache;
	struct list_head	list;
} cblk_t;

typedef struct _session {
	ecm_uint32	sid;
	ecm_uint32	bid;
	interval_t	*preceding;
	interval_t	*following;
	media_t		*media;
} session_t;

static ecm_ptrs_t	*ptrs_media;

#ifdef PARANOIA

static void
show_media_interval_infos(media_t *media)
{
	interval_t	*interval;
	struct list_head	*lp;

	list_for_each (lp, &media->intervals) {
		interval = list_entry(lp, interval_t, list_media);
		printf("[%u:%u] ", interval->follower->bid, interval->precedent->bid);
		{
			cblk_t	*cblk;
			struct list_head *lq;
			list_for_each (lq, &interval->cblks) {
				cblk = list_entry(lq, cblk_t, list);
				printf("%u ", cblk->bcache->bid);
			}
		}
	}
	printf("\n");
}

static void
show_all_interval_infos(void)
{
	int	i;

	for (i = 0; i < 1; i++) {
		show_media_interval_infos(ptrs_media->pdata[i]);
	}
}

#define SHOW_ALL_INTERVAL_INFOS()	show_all_interval_infos()

#else

#define SHOW_ALL_INTERVAL_INFOS()	do {} while (0)

#endif

static void
collect_bcache(interval_t *interval, ecm_uint32 mid, ecm_uint32 bid_start, ecm_uint32 bid_end)
{
	bcache_t	*bcache;
	ecm_uint32	bid;

	for (bid = bid_start; bid <= bid_end; bid++) {
		cblk_t	*cblk;

		bcache = bc_find_bcache(mid, bid);
		if (bcache == NULL)
			continue;
		cblk = (cblk_t *)bcache->priv;
		ECMASSERT(cblk->bcache == bcache);

		if (list_empty(&cblk->list))
			continue;

		list_del_init(&cblk->list);
		list_add_tail(&cblk->list, &interval->cblks);
	}
}

static void
collect_cache(interval_t *interval)
{
	session_t	*follower, *precedent;
	ecm_uint32	bid;
	ecm_uint32	mid;
	cblk_t		*cblk;
	struct list_head	*lp;

	if (!cblk_collect_enabled)
		return;

	follower = interval->follower;
	precedent = interval->precedent;

	mid = follower->media->mid;
	bid = follower->bid;

	list_for_each (lp, &interval->cblks) {
		cblk = list_entry(lp, cblk_t, list);
		ECMASSERT(bid <= cblk->bcache->bid);
		if (bid < cblk->bcache->bid) {
			collect_bcache(interval, mid, bid, cblk->bcache->bid - 1);
		}
		bid = cblk->bcache->bid + 1;
	}
	if (bid <= precedent->bid) {
		collect_bcache(interval, mid, bid, precedent->bid);
	}
}

/**
 * @brief find the included interval
 */
static interval_t *
find_interval(ecm_uint32 mid, ecm_uint32 bid, interval_t *interval)
{
	media_t	*media;
	struct list_head	*lp;

	ECMASSERT(bid > 0);

	media = ecm_ptrs_get(ptrs_media, mid);
	ECMASSERT(media != NULL);

	if (interval == NULL) {
		if (list_empty(&media->intervals))
			return NULL;

		lp = media->intervals.next;
	}
	else
		lp = &interval->list_media;

	for (; lp != &media->intervals; lp = lp->next) {
		session_t	*follower, *precedent;

		interval = list_entry(lp, interval_t, list_media);
		follower = interval->follower;
		precedent = interval->precedent;

		ECMASSERT(follower != NULL && precedent != NULL);
		ECMASSERT(follower->bid <= precedent->bid);

		if (bid >= follower->bid && bid <= precedent->bid)
			return interval;
	}

	return NULL;
}

/**
 * sort interval again
 */
static void
sort_interval(interval_t *interval, ECMBOOL forward)
{
	struct list_head	*lp, *first;
	ecm_uint32	size;
	interval_t	*intv_list;

	ECMASSERT(!list_empty(&interval->list));

	first = (forward) ? interval->list.next : interval->list.prev;
	list_del(&interval->list);

	size = interval->size;

	if (forward) {
		for (lp = first; lp != &intervals; lp = lp->next) {
			intv_list = list_entry(lp, interval_t, list);
			if (size > intv_list->size) {
				list_add_tail(&interval->list, &intv_list->list);
				return;
			}
		}
		list_add_tail(&interval->list, &intervals);
	}
	else {
		for (lp = first; lp != &intervals; lp = lp->prev) {
			intv_list = list_entry(lp, interval_t, list);
			if (size < intv_list->size) {
				list_add(&interval->list, &intv_list->list);
				return;
			}
		}
		list_add(&interval->list, &intervals);
	}
}

static interval_t *
create_interval(session_t *precedent, session_t *follower)
{
	interval_t	*interval;

	ECMASSERT(precedent->bid >= follower->bid);

	interval = (interval_t *)ecm_malloc(sizeof(interval_t));
	ECMASSERT(interval != NULL);

	interval->size = precedent->bid - follower->bid;
	interval->follower = follower;
	interval->precedent = precedent;

	follower->following = interval;
	precedent->preceding = interval;

	INIT_LIST_HEAD(&interval->cblks);
	INIT_LIST_HEAD(&interval->list);
	INIT_LIST_HEAD(&interval->list_media);

	n_intervals++;

	return interval;
}

static void
free_interval(interval_t *interval)
{
	list_del(&interval->list);
	list_del(&interval->list_media);
	ecm_free(interval);

	ECMASSERT(n_intervals > 0);
	n_intervals--;
}

static void
build_interval(session_t *precedent, session_t *follower)
{
	interval_t	*interval;

	ECMASSERT(precedent != NULL && follower != NULL);

	ECMASSERT(follower->following == NULL);
	ECMASSERT(precedent->preceding == NULL);

	interval = create_interval(precedent, follower);

	list_add(&interval->list, &intervals);
	sort_interval(interval, ECM_TRUE);

	if (precedent->following == NULL && follower->preceding == NULL) {
		ECMASSERT(list_empty(&precedent->media->intervals));
		list_add(&interval->list_media, &precedent->media->intervals);
	}
	else if (precedent->following == NULL) {
		list_add(&interval->list_media, &follower->preceding->list_media);
	}
	else {
		ECMASSERT(follower->preceding == NULL);
		list_add_tail(&interval->list_media, &precedent->following->list_media);
	}

	collect_cache(interval);
}

/**
 * @brief get cache blocks from splitted interval
 */
static void
split_cblks(interval_t *interval, session_t *session)
{
	ecm_uint32	bid = session->bid;
	cblk_t	*cblk;
	struct list_head	*pcblks;
	struct list_head	*lp, *next;

	pcblks = &session->preceding->cblks;
	list_for_each_n (lp, &interval->cblks, next) {
		cblk = list_entry(lp, cblk_t, list);

		if (bid < cblk->bcache->bid)
			return;

		list_del(&cblk->list);
		list_add_tail(&cblk->list, pcblks);
	}
}

static void
split_interval(interval_t *interval, session_t *session)
{
	session_t	*follower, *precedent;
	interval_t	*interval_new;

	follower = interval->follower;
	precedent = interval->precedent;

	interval_new = create_interval(session, follower);

	interval->follower = session;
	session->following = interval;

	sort_interval(interval, ECM_TRUE);

	list_add(&interval_new->list, &intervals);
	sort_interval(interval_new, ECM_TRUE);

	list_add_tail(&interval_new->list_media, &interval->list_media);
	split_cblks(interval, session);
}

/**
 * @brief Insert newly or cut-out session to form a interval.
 */
static void
putdown_session(session_t *session, interval_t *hint)
{
	media_t		*media = session->media;
	interval_t	*interval;

	if (list_empty(&media->intervals)) {
		/* media has no interval */
		session_t	*solo;
		session_t	*follower, *precedent;

		if ((solo = media->session) == NULL) {
			media->session = session;
			return;
		}

		media->session = NULL;

		if (solo->bid >= session->bid) {
			follower = session;
			precedent = solo;
		}
		else {
			follower = solo;
			precedent = session;
		}
		build_interval(precedent, follower);
		return;
	}
		
	interval = find_interval(media->mid, session->bid, hint);
	if (interval == NULL) {
		session_t	*follower;

		interval = list_entry(media->intervals.next, interval_t, list_media);
		follower = interval->follower;

		if (session->bid <= follower->bid)
			build_interval(follower, session);
		else {
			session_t	*precedent;

			interval = list_entry(media->intervals.prev, interval_t, list_media);
			precedent = interval->precedent;
			ECMASSERT(session->bid >= precedent->bid);
			build_interval(session, precedent);
		}
	}
	else {
		split_interval(interval, session);
	}
}

static session_t *
create_session(ecm_uint32 sid, ecm_uint32 mid, ecm_uint32 bid)
{
	session_t	*session;

	session = (session_t *)ecm_malloc(sizeof(session_t));
	session->sid = sid;
	session->bid = bid;
	session->preceding = NULL;
	session->following = NULL;
	session->media = (media_t *)ecm_ptrs_get(ptrs_media, mid);
	ECMASSERT(session->media != NULL);

	ecm_hashtable_insert(hash_session, session, sizeof(sid), &sid);

	return session;
}

static void
free_session(session_t *session)
{
	ecm_hashtable_remove(hash_session, sizeof(ecm_uint32), &session->sid);
	ecm_free(session);
}

/**
 * @brief cut out session. It may cause intervals to be merged or deleted.
 */
static void
cut_session(session_t *session)
{
	interval_t	*preceding, *following;

	preceding = session->preceding;
	following = session->following;

	if (preceding == NULL && following == NULL) {
		session->media->session = NULL;
	}
	else if (preceding != NULL && following != NULL) {
		session_t	*precedent = following->precedent;

		preceding->precedent = precedent;
		precedent->preceding = preceding;
		preceding->size += following->size;

		list_splice(&following->cblks, preceding->cblks.prev);
		free_interval(following);

		sort_interval(preceding, ECM_FALSE);
	}
	else {
		session_t	*partner;
		interval_t	*deleted;

		if (preceding != NULL) {
			deleted = preceding;
			partner = preceding->follower;
			partner->following = NULL;
		}
		else {
			deleted = following;
			partner = following->precedent;
			partner->preceding = NULL;
		}
		
		list_splice(&deleted->cblks, &free_list);
		free_interval(deleted);

		if (partner->following == NULL && partner->preceding == NULL) {
			ECMASSERT(partner->media->session == NULL);
			partner->media->session = partner;
		}
	}

	session->preceding = NULL;
	session->following = NULL;
}

static session_t *
get_session(ecm_uint32 sid, ecm_uint32 mid, ecm_uint32 bid)
{
	session_t	*session;

	session = (session_t *)ecm_hashtable_get(hash_session, sizeof(sid), &sid);
	if (session == NULL) {
		session = create_session(sid, mid, bid);
		putdown_session(session, NULL);
	}
	else {
		if (bid != session->bid + 1) {
			cut_session(session);
			session->bid = bid;
			putdown_session(session, NULL);
		}
		else
			session->bid = bid;
	}

	return session;
}

static void
insert_cblk(interval_t *interval, cblk_t *cblk)
{
	struct list_head	*lp;
	cblk_t	*cblk_list;

	ECMASSERT(list_empty(&cblk->list));

	for (lp = interval->cblks.prev; lp != &interval->cblks; lp = lp->prev) {
		cblk_list = list_entry(lp, cblk_t, list);

		ECMASSERT(cblk_list->bcache->mid == cblk->bcache->mid);
		ECMASSERT(cblk_list->bcache->bid != cblk->bcache->bid);

		if (cblk->bcache->bid > cblk_list->bcache->bid) {
			list_add(&cblk->list, &cblk_list->list);
			return;
		}
	}
	list_add(&cblk->list, &interval->cblks);
}

static void
ic_create(bcache_t *bcache)
{
	cblk_t	*cblk;

	cblk = (cblk_t *)ecm_malloc(sizeof(cblk_t));
	bcache->priv = cblk;

	cblk->bcache = bcache;
	list_add(&cblk->list, &free_list);
}

static void
ic_hit(bcache_t *bcache)
{
	cblk_t	*cblk = (cblk_t *)bcache->priv;

	list_del_init(&cblk->list);
}

static bcache_t *
ic_replace(ecm_uint32 mid, ecm_uint32 bid)
{
	cblk_t	*cblk;

	if (!list_empty(&free_list))
		cblk = list_entry(free_list.next, cblk_t, list);
	else {
		interval_t	*interval;
		struct list_head	*lp;

		list_for_each (lp, &intervals) {
			interval = list_entry(lp, interval_t, list);
			if (!list_empty(&interval->cblks)) {
				cblk = list_entry(interval->cblks.prev, cblk_t, list);
				goto out;
			}
		}
		return NULL;
	}
out:
	list_del_init(&cblk->list);
	return cblk->bcache;
}

static void
ic_put(ecm_uint32 sid, bcache_t *bcache)
{
	session_t	*session;
	cblk_t	*cblk = (cblk_t *)bcache->priv;
	interval_t	*preceding;

	session = (session_t *)ecm_hashtable_get(hash_session, sizeof(sid), &sid);
	ECMASSERT(session != NULL);

	preceding = session->preceding;
	if (preceding == NULL) {
		list_add_tail(&cblk->list, &free_list);
		return;
	}

	insert_cblk(preceding, cblk);
}

static void
ic_access(ecm_uint32 sid, ecm_uint32 mid, ecm_uint32 bid)
{
	session_t	*session;
	interval_t	*preceding, *following;
	ecm_uint32	old_size, new_size;

	session = get_session(sid, mid, bid);
	ECMASSERT(session != NULL);

	preceding = session->preceding;
	following = session->following;

	/* check if a follower has preceded its precedent */
	if (following != NULL && session->bid > following->precedent->bid) {
		cut_session(session);
		/* following stream has gone */
		putdown_session(session, preceding);
		return;
	}

	if (preceding != NULL) {
		session_t	*follower = preceding->follower;

		ECMASSERT(preceding->precedent == session);

		ECMASSERT(session->bid >= follower->bid);

		old_size = preceding->size;
		new_size = bid - follower->bid;

		if (old_size != new_size) {
			preceding->size = new_size;
			sort_interval(preceding, old_size > new_size);
		}
	}

	if (following != NULL) {
		session_t	*precedent = following->precedent;

		ECMASSERT(following->follower == session);
		ECMASSERT(session->bid <= precedent->bid);

		old_size = following->size;
		new_size = precedent->bid - bid;

		if (old_size != new_size) {
			following->size = new_size;
			sort_interval(following, old_size > new_size);
		}
	}
}

static void
ic_leave(ecm_uint32 sid)
{
	session_t	*session;

	session = (session_t *)ecm_hashtable_get(hash_session, sizeof(sid), &sid);
	ECMASSERT(session != NULL);

	cut_session(session);
	free_session(session);
}

static void
ic_add_media(ecm_uint32 bid_max)
{
	media_t		*media;

	media = (media_t *)ecm_malloc(sizeof(media_t));
	media->mid = ptrs_media->count + 1;
	media->session = NULL;
	media->bid_max = bid_max;
	INIT_LIST_HEAD(&media->intervals);
	ecm_ptrs_add(ptrs_media, media);
}

static const char *
ic_init(ecm_uint32 cache_blksize, ecm_uint32 n_caches)
{
	ptrs_media = ecm_ptrs_new(16);

	hash_session = ecm_hashtable_create(32);

	return POLICY_NAME;
}

static void
ic_setup(const sr_t *sr_mod_conf)
{
}

static void
ic_show_conf(void)
{
	bc_printlog("Cache Collection Enabled:    %s\n", cblk_collect_enabled ? "Yes": "No");
}

static void
ic_fini(void)
{
	SHOW_ALL_INTERVAL_INFOS();
}

blockcache_op_t	bcache_op = {
	ic_init,
	ic_setup,
	ic_show_conf,
	ic_add_media,

	ic_create,
	ic_hit,
	ic_replace,
	ic_put,

	ic_access,
	ic_leave,
	ic_fini
};
